package com.example.lettcode._202410._20241014;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/*
56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，
并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
public class Qu_jian_he_bing {

    public static void main(String[] args) {
        int[][] intervals = {{2,8},{1,3},{8,10},{15,18}};
        int[][] merge = merge3(intervals);
        for (int i = 0; i < merge.length; i++) {
            for (int j = 0; j < merge[i].length; j++) {
                System.out.print(merge[i][j] + "");
            }
            System.out.println();
        }
    }

    public static int[][] merge3(int[][] intervals) {
        if (intervals == null || intervals.length <=1) {
            return intervals;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int[] prev = intervals[0];
        int[] cur;
        int k = 0;

        for (int i = 1; i < intervals.length; i++) {
            cur = intervals[i];
            if (prev[1] >= cur[0]) {
                int m = Math.max(prev[1], cur[1]);
                prev[1] = m;
            } else {
                intervals[k++] = prev;
                prev = cur;
            }
        }
        intervals[k++] = prev;
        return Arrays.copyOfRange(intervals, 0, k);
    }

    public static int[][] merge2(int[][] intervals) {
        if (intervals == null || intervals.length <=1) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[] pre = intervals[0];
        int[] cur;
        int k = 0;

        for (int i = 1; i < intervals.length; i++) {
            cur = intervals[i];
            if (cur[0] <= pre[1]) {
                int max = Math.max(pre[1], cur[1]);
                pre[1] = max;
            } else {
                intervals[k++] = pre;
                pre = cur;
            }
        }
        intervals[k++]=pre;
        return Arrays.copyOfRange(intervals, 0, k);
    }

    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <=1) {
            return intervals;
        }

        int endIndex = 1;
        int startIndex = 0;
        List<int[]> list = new ArrayList<>();
        while (endIndex <= intervals.length) {
            int[] ints = new int[2];
            if (intervals[endIndex-1][0] > intervals[startIndex][intervals[startIndex].length-1]) {
                ints = new int[2];
                ints[0] = intervals[startIndex][0];
                ints[1] = intervals[endIndex-1][intervals[endIndex-1].length-1];
                list.add(ints);
            } else {
                ints[0] = intervals[startIndex][0];
                ints[1] = intervals[endIndex-1][intervals[endIndex-1].length-1];
            }
            endIndex++;

        }
        int[][] ints = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        return ints;
    }
}
